package sortAlgorithm.quickSort;

import java.util.Arrays;

/**
 * @author： pang-yun
 * @date： 2021-09-25 11:05
 * 功能目的 ：用于 快速排序  冒泡的进阶版本
 * <p>
 * 递归
 */

public class QuickSort {

    public static void main(String[] args) {
        Integer[] arr={10,9,8,7,6,5,4,3,3,2,1,3};
        QuickSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 比较v 元素是否小于 w元素
     */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * 数组 元素 i 和 J 交换位置
     */
    private static void exchange(Comparable[] arr, int i, int j) {
        Comparable t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    /**
     * 对数组内元素进行排序
     */
    public static void sort(Comparable[] arr) {
        int low = 0;
        int high = arr.length;
        sort(arr, low, high - 1);
    }

    /**
     * 对数组a中 从索引lo 到 hi 之间的元素进行排序
     */
    private static void sort(Comparable[] arr, int low, int high) {
        // 首先做安全性 校验
        if (high < low) return;

        // 需要对数组进行分组 左子组  右子组
        int partition = partition(arr, low, high);  // 返回的是 分界值 变换后的索引

        //让左子组有序
        sort(arr, low, partition - 1);
        // 让右子组有序
        sort(arr, partition + 1, high);
    }

    /**
     * 对数组a中，从索引lo 到 hi 之间的元素进行分组 并返回分组界限对应的索引
     */
    public static int partition(Comparable[] arr, int low, int high) {
        // 确定 分界值
        Comparable key = arr[low];
        // d定义左右两个指针
        int left = low;
        int right = high + 1;  // 必须+1  否则下面的 --right 不能实现

        //开始切分
        while (true) {
            // 先从右向左扫描 移动right 指针 找到一个比分界值小的元素 停止
            while (less(key, arr[--right])) {
                if (right == low) break;
            }
            // left指针 从 左向右移动 找到一个比分界值大的元素 停止
            while (less(arr[++left], key)) {
                if (left == high) break;
            }
            // 再判断 left>=right 如果是 则证明 扫描完毕 如果不是 则需要交换元素
            if (left >= right) {
                break;
            } else {
                exchange(arr, left, right);
            }
        }

        // 交换分界值
        exchange(arr, low, right);

        return right;
    }
}
